πŸ“‚ μ΄μ§„νƒμƒ‰νŠΈλ¦¬(Binary Search Tree)

@Seongukbaek Posted May 28, 2022 Β· Updated May 28, 2022 Β· 5 min read

🧷 이진 탐색 트리

이진 탐색 + μ—°κ²° 리슀트

  • 이진 탐색 : 탐색에 μ†Œμš”λ˜λŠ” μ‹œκ°„λ³΅μž‘λ„λŠ” O(logN)O(logN), ν•˜μ§€λ§Œ μ‚½μž…, μ‚­μ œκ°€ λΆˆκ°€λŠ₯
  • μ—°κ²° 리슀트 : μ‚½μž…, μ‚­μ œμ˜ μ‹œκ°„λ³΅μž‘λ„λŠ”O(1)O(1), νƒμƒ‰ν•˜λŠ” μ‹œκ°„λ³΅μž‘λ„κ°€ O(N)O(N)

이 두 κ°€μ§€λ₯Ό ν•©ν•˜μ—¬ μž₯점을 λͺ¨λ‘ μ–»μ–΄ 효율적인 탐색 λŠ₯λ ₯κ³Ό 자료의 μ‚½μž…, μ‚­μ œλ„ κ°€λŠ₯ν•˜κ²Œ ν•˜λŠ” 이진 탐색 트리

πŸͺš νŠΉμ§•

  • λ…Έλ“œμ— μ €μž₯된 ν‚€λŠ” 유일 (쀑볡이 μ—†μ–΄μ•Ό 함)
  • 각 λ…Έλ“œμ˜ μžμ‹μ΄ 2개 μ΄ν•˜
  • 각 λ…Έλ“œμ˜ μ™Όμͺ½ μžμ‹μ€ λΆ€λͺ¨λ³΄λ‹€ μž‘κ³ , 였λ₯Έμͺ½ μžμ‹μ€ λΆ€λͺ¨λ³΄λ‹€ 큼
  • μ™Όμͺ½κ³Ό 였λ₯Έμͺ½ μ„œλΈŒ νŠΈλ¦¬λ„ 이진 탐색 트리

쀑볡이 μ—†μ–΄μ•Ό ν•˜λŠ” 이유

: 검색 λͺ©μ  자료ꡬ쑰인데, ꡳ이 쀑볡이 λ§Žμ€ κ²½μš°μ— 트리λ₯Ό μ‚¬μš©ν•˜μ—¬ 검색 속도λ₯Ό 느리게 ν•  ν•„μš”κ°€ μ—†λ‹€.

이진 탐색 트리의 μˆœνšŒλŠ” "μ€‘μœ„ 순회(inorder)" λ°©μ‹μœΌλ‘œ, μ •λ ¬λœ μˆœμ„œλ‘œ 읽을 수 μžˆλ‹€.

πŸͺš BST 핡심 μ—°μ‚°

  • 검색
  • μ‚½μž…
  • μ‚­μ œ
  • 트리 생성, μ‚­μ œ

πŸͺš μ‹œκ°„ λ³΅μž‘λ„

λ…Έλ“œ κ°œμˆ˜κ°€ N개일 λ•Œ,

  • κ· λ“± 트리: O(logN)O(logN)
  • 편ν–₯ 트리: O(N)O(N)

μ‚½μž…, 검색, μ‚­μ œ μ‹œκ°„λ³΅μž‘λ„λŠ” 트리의 Depth에 λΉ„λ‘€

μ‚­μ œμ˜ 3κ°€μ§€ 경우

  1. μžμ‹μ΄ μ—†λŠ” 리프 λ…Έλ“œμΌ λ•Œ -> κ·Έλƒ₯ μ‚­μ œ!
  2. μžμ‹μ΄ 1개인 λ…Έλ“œμΌ λ•Œ -> μžμ‹ λ…Έλ“œμ™€ κ΅ν™˜ ν›„, μ‚­μ œ
  3. μžμ‹μ΄ 2개인 λ…Έλ“œμΌ λ•Œ -> 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œμ—μ„œ κ°€μž₯ μž‘μ€ κ°’ λ˜λŠ” μ™Όμͺ½ μžμ‹ λ…Έλ“œμ—μ„œ κ°€μž₯ 큰 κ°’κ³Ό κ΅ν™˜ ν›„, μ‚­μ œ

편ν–₯된 νŠΈλ¦¬λŠ” μ‹œκ°„λ³΅μž‘λ„κ°€ O(N)O(N)μ΄λ―€λ‘œ 트리λ₯Ό μ‚¬μš©ν•  μ΄μœ κ°€ μ—†λ‹€!

  • 이λ₯Ό λ°”λ‘œ μž‘λ„λ‘ Rebalancing ν•˜λŠ” κ°œμ„ λ°©μ•ˆμ΄ AVL Tree, RedBlack Tree
class BinarySearchTree { public class Node { int data; Node left; Node right; public Node(int data) { this.data = data; this.left = null; this.right = null; } } public Node root; public BinarySearchTree() { this.root = null; } public boolean find(int id) { Node cur = root; while(cur != null) { if (cur.data == id) return true; else if(cur.data > id) cur = cur.left; else cur = cur.right; } return false; } public boolean delete(int id) { Node parent = root; Node cur = root; boolean isLeftChild = false; while(cur.data != id) { parent = cur; if (cur.data > id) { isLeftChild = true; cur = cur.left; } else { isLeftChild = false; cur = cur.right; } if (cur == null) return false; } // case1. μžμ‹ λ…Έλ“œκ°€ μ—†λŠ” 경우 -> κ·Έλƒ₯ μ‚­μ œ if (cur.left == null && cur.right == null) { if (cur == root) root = null; if (isLeftChild == true) parent.left = null; else parent.right = null; } // case2. μžμ‹ λ…Έλ“œκ°€ 1개인 경우 -> κ΅ν™˜ ν›„ μ‚­μ œ else if (cur.right == null) { if (cur == root) root = cur.left; else if (isLeftChild) parent.left = cur.left; else parent.right = cur.left; } else if (cur.left == null) { if (cur == root) root = cur.left; else if (isLeftChild) parent.left = cur.right; else parent.right = cur.right; } // case3. μžμ‹ λ…Έλ“œκ°€ 2개인 경우 -> 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œ 쀑 μ΅œμ†Ÿκ°’κ³Ό κ΅ν™˜ ν›„ μ‚­μ œ else if (cur.left != null && cur.right != null) { Node minNode = getMin(cur); if (cur == root) root = minNode; else if (isLeftChild) parent.left = minNode; else parent.right = minNode; minNode.left = cur.left; } return true; } // 였λ₯Έμͺ½ μ„œλΈŒ νŠΈλ¦¬μ—μ„œ μ΅œμ†Ÿκ°’μ„ λ°˜ν™˜ public Node getMin(Node deleteNode) { Node minNode = null; Node minNodeParent = null; Node cur = deleleNode.right; while(cur != null) { minNodeParent = minNode; minNode = cur; cur = cur.left; } if (minNode != deleleNode.right) { minNodeParent.left = minNode.right; minNode.right = deleleNode.right; } return minNode; } public void insert(int id) { Node newNode = new Ndoe(id); if (root == null) { root = newNode; return; } Node cur = root; Node parent = null; while(true) { parent = cur; if (id < cur.date) { cur = cur.left; if (cur == null) { parent.left = newNode; return; } } else { cur = cur.right; if (cur == null) { parent.right = newNode; return; } } } } public void print(Node root) { if (root != null) { print(root.left); System.out.println(" " + root.date); print(root.right); } } }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€